package examination;

import java.util.Scanner;

/**
 * Created by zxc on 2018/9/17.
 * 1. 给你五种零钱1,5,10,20,50的纸币，给定一个金额，写出所有可能的找零个数   https://blog.csdn.net/u012150590/article/details/52410916
 * 2. 假如给你这些面值的硬币{25, 21, 10, 5, 1 }，问需要对63进行找零，需要的最少硬币数为？ https://blog.csdn.net/a754112602/article/details/81110642
 */
public class SmallChange {

        private static int count=0;
        static int RMB[]={1,5,10,20,50};

        public static void main(String[] args) {
            // TODO Auto-generated method stub
            // 100a+50b+20c+10d+5e+2f+g=n
            Scanner in=new Scanner(System.in);
            while (in.hasNextInt()) {
                int n=in.nextInt();
                if (n==0) {
                    break;
                }
                //  动态规划方法
                int i=0;
                for ( i = 4; i >=0&&RMB[i]>n; i--) ;  // 找到最大的可找零钱的下标
                System.out.println(find(n,2));
            }

        }

        // 找到可找零钱的方案数
        private static int find(int n, int i) {
            // TODO Auto-generated method stub
            if (n<0) {
                return 0;
            }
            if (n<=1||RMB[i]==1) {
                return 1;
            }

            return find(n-RMB[i], i)+find(n, i-1);        // 第一项为包括 RMB[i] 的方案数，第二项为不包括的方案数
        }


    /**
         * 硬币找零：动态规划算法
         *
         * @param values
         *            :保存不同硬币的币值的数组
         * @param valueKinds
         *            :values数组的大小
         * @param money
         *            :需要找零的面值
         * @param coinsUsed
         *            :保存面值为i的纸币找零所需的最小硬币数
         */
        public static void makeChange(int[] values, int valueKinds, int money,
                                      int[] coinsUsed) {

            coinsUsed[0] = 0;

            // 对所有数额都找零(从小到大)，即保存子问题的解以备用，即填表
            for (int cents = 1; cents <= money; cents++) {
                // 当用最小币值的硬币找零时，所需硬币数量最多
                //这里最小面值为1，那n元就需要n个硬币，所以是最多
                int minCoins = cents;

                // 遍历每一种面值的硬币，看是否可作为找零的其中之一
                //[25, 21, 10, 5, 1]
                for (int kind = 0; kind < valueKinds; kind++) {
                    // 若当前面值的硬币小于当前的cents则分解问题并查表
                    if (values[kind] <= cents) {
                        int temp = coinsUsed[cents - values[kind]] + 1;
                        if (temp < minCoins) {
                            minCoins = temp;
                        }
                    }
                }
                // 保存最小硬币数
                coinsUsed[cents] = minCoins;

                System.out.println("面值为 " + (cents) + " 的最小硬币数 : "
                        + coinsUsed[cents]);
            }
        }

        /*public static void main(String[] args) {

            // 硬币面值预先已经按降序排列
            int[] coinValue = new int[] { 25, 21, 10, 5, 1 };
            // 需要找零的面值
            int money = 63;
            // 保存每一个面值找零所需的最小硬币数，0号单元舍弃不用，所以要多加1
            int[] coinsUsed = new int[money + 1];

            makeChange(coinValue, coinValue.length, money, coinsUsed);
        }*/

}
